package baseclass.l_string;

/**
 * 给定一个字符串str1，只能往str1的后面添加字符变成str2，要求str2整体是回文，并且最短。
 * 如：
 * Str1 = ABC12321,str2=ABC12321CBA
 * <p>
 * 分析：其实就是最大尺度的利用str1 以 最后一个元素为结束的回文。也就是在Manacher算法中，
 * 第一个达到最后一个元素的回文12321，然后把之前的ABC倒叙拼接即可。
 *
 * @date 2020/3/6 16:50
 */
public class Code08_ManacherAppPalindRome {
    public static String getPalindRome(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] chars = getModify(s);
        int R = -1;
        int centerR = -1;
        int max = 0;
        int maxCenter = -1;
        int[] pArr = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            if (i <= R) {
                //情况2的 case1,2,3.case3中还会进入while循环。
                pArr[i] = Math.min(pArr[2 * centerR - i], R - i + 1);
            } else {
                pArr[i] = 1;
            }
            //往两侧扩
            while (i + pArr[i] < chars.length && i - pArr[i] >= 0) {
                //情况2的case1和case2不符合，直接跳出
                if (chars[i + pArr[i]] == chars[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            //如果产生了新的右边界
            if (i + pArr[i] - 1 > R) {
                R = i + pArr[i] - 1;
                centerR = i;
                //这里判断是否达到了最右边界
                if(R == chars.length - 1){
                    maxCenter = i;
                    System.out.println("maxCenter = " + maxCenter);
                    max = pArr[i];
                    break;
                }
            }
            //如果最大值发生了变化，更新最大值
            if (max < pArr[i]) {
                max = pArr[i];
                maxCenter = i;
            }

        }

        StringBuffer sb = new StringBuffer();
        //终止index是 maxCenter - (max-1) = maxCenter-max + 1
        for (int i = 0; i <= maxCenter - max; i++) {
            if(chars[i] != '#') sb.append(chars[i]);
        }
        return s+sb.reverse().toString();
       /* //回文串长度是max -1，回文范围是[maxCenter-(max-1),maxCenter+(max-1)+1) ,分析如下
        //如果是奇数个，如.....#1#....，中心是数，此时max=2为偶数，所以要减少1 = 1。
        // 起始坐标是maxRightIndex-(max-1)，终止是maxRightIndex+(max-1),但截取串要+1
        //如果是偶数个，如.....#1#1#....,中心是#，此时max=3为奇数，所以要减少1 = 2。
        // 起始坐标是maxRightIndex-(max-1),终止是maxRightIndex+(max-1),但截取串要+1
        return new String(chars).substring(maxCenter - (max - 1), maxCenter + (max - 1) + 1)
                .replace("#", "");
*/

    }

    private static char[] getModify(String s) {
        StringBuffer sb = new StringBuffer();
        sb.append("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString().toCharArray();
    }
    public static void main(String[] args) {
        System.out.println(getPalindRome("a1aa"));
        System.out.println(getPalindRome("a1aba"));
    }
}
